/**
 * 回溯+剪枝
 * 有左括号 可以选左括号
 * 右括号比左括号少 选左括号 保持左右相等

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
 */
//left right 表示的是当前剩余的括号数
var generateParenthesis = function(n) {
  let res = [];
  const dfs = function(left,right,str) {
    if(str.length == 2*n) {  //回溯结束 构建完成
      res.push(str);
      return;
    }
    if(left > 0) {
      dfs(left-1,right,str+'(')
    }
    if(left < right) { 
      dfs(left,right-1,str+')')
    }
  }
  dfs(n,n,'')
  return res;
};
console.log(generateParenthesis(3)) //["((()))","(()())","(())()","()(())","()()()"]
console.log(generateParenthesis(1)) //["()"]